package top.firejames.io;

import top.firejames.util.ArrayUtils;

/**
 * @auther 夏浩
 * @creat 2021-09-2021/9/24-10:28
 */
public class Sort {


    /**
     * 二路归并排序（分而治之+归并）
     * @param data
     * @param start
     * @param end
     */
    public static void mergeSort(int[] data, int start, int end) {
        if (ArrayUtils.empty(data)) return;
        if (start >= end) return;
        int middle = (start + end) / 2;
        mergeSort(data, start, middle);
        mergeSort(data, middle + 1, end);
        merge(data, start, middle + 1, end);
    }

    /**
     * 合并
     * @param data
     * @param low
     * @param mid
     */
    public static void merge(int[] data, int low, int mid, int high) {
        int i = low;
        int j = mid;
        int index = 0;
        int[] merge = new int[high - low + 1];
        while (i <= mid - 1 && j <= high) {
            if (data[i] <= data[j]) {
                if(data[i] == data[j]) {
                    merge[index++] = data[j++];
                }
                merge[index++] = data[i++];
            }else {
                merge[index++] = data[j++];
            }
        }
        while (i <= mid - 1) {
            merge[index++] = data[i++];
        }
        while (j <= high) {
            merge[index++] = data[j++];
        }
        for (int k = 0; k < index; k++) {
            data[low + k] = merge[k];
        }
    }

}
